#include <stdio.h>
#include <iostream>
#include <vector>

using namespace std;

class Solution {
    void backtrack(vector<vector<int>> &answer, vector<int> &path, int start, int sum, int k, int n) {
        if (path.size() == k && sum == n) {
            answer.push_back(path);
            return;
        }

        if (path.size() > k || sum > n || start > n) return;

        for (int i = start; i <= 9; i++) {
            path.push_back(i);
            backtrack(answer, path, i+1, sum+i, k, n);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<vector<int>> answer;
        vector<int> path;
        backtrack(answer, path, 1, 0, k, n);
        return answer;
    }
};

int main(void)
{

    cout << "#216. 组合总和 III" << endl;
    vector<vector<int>> anss = Solution().combinationSum3(3, 7);

    for (auto e: anss) {
        for (auto it: e)
            cout << it << ", ";
        cout << endl;
    }
    return 0;
}